import math
from collections import Counter

def euclidean_distance(p1, p2):
    #计算两个点之间的欧氏距离
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))
def knn_predict(data, labels, x, k=3, weighted=False):
    #手动实现K近邻
    if len(data) != len(labels) or not data or k <= 0 or k > len(data):
        raise ValueError("数据标签不匹配、数据为空或 k 值无效")
    # 计算距离并排序
    neighbors = sorted(
        [(euclidean_distance(x, p), lbl) for p, lbl in zip(data, labels)],
        key=lambda d: d[0]
    )[:k]
    if weighted:
        # 加权投票
        vote_dict = {}
        for dist, lbl in neighbors:
            vote_dict[lbl] = vote_dict.get(lbl, 0) + 1 / (dist + 1e-5)
        return max(vote_dict, key=vote_dict.get)
    else:
        # 多数投票：直接提取标签统计
        return Counter(lbl for _, lbl in neighbors).most_common(1)[0][0]

# —————————— 主函数测试 ——————————
if __name__ == "__main__":
    train_data = [
        [1,1],[2,2],[1,2], [5,5],[6,6],[5,6], [8,2],[9,3],[8,1]]
    train_labels = [0]*3 + [1]*3 + [2]*3  # 简化标签定义
    test_points = [[1.5,1.5], [5.5,5.5], [8.5,2.0], [3,3]]
    print("KNN 分类测试 (k=3):\n" + "-"*50)
    for x in test_points:
        pred = knn_predict(train_data, train_labels, x)
        pred_w = knn_predict(train_data, train_labels, x, weighted=True)
        print(f"测试点 {x}: 多数投票→{pred}, 加权投票→{pred_w}")